//30. 串联所有单词的子串

#include <string>
#include <vector>
#include <map>
using namespace std;

class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ret;
        map<string, int> hash1; // 保存 words 里面所有单词的频次
        for(auto& word : words) hash1[word]++;

        int len = words[0].size(), m = words.size();
        for(int i = 0; i < len; i++) // 执行 len 次
        {
            map<string, int> hash2; // 维护窗口内单词的频次
            for(int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);
                hash2[in]++; // 进窗口
                // 判断hash1中是否存在in字符串，可以优化不存在后插入的情况
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++; // 维护 count
                // 判断
                if(right - left + 1 > len * m)
                {
                    string out = s.substr(left, len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--; // 维护 count
                    hash2[out]--; // 出窗口
                    left += len;
                }
                // 更新结果
                if(count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};